package MultiSourceShortestPath;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class MapOfHighestPeak {
    // 辅助向量数组
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,-1,1};

    // 辅助布尔数组
    //boolean[][] visit;

    int m; // 对应 x 坐标
    int n; // 对应 y 坐标
    public int[][] highestPeak(int[][] isWater) {
        m = isWater.length;
        n = isWater[0].length;

        //visit = new boolean[m][n];
        int[][] dp = new int[m][n]; // 结果数组
        for(int[] row : dp) {
            Arrays.fill(row, -1);
        }

        // 找到 0 位置坐标, 直接存入队列中
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(isWater[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    dp[i][j] = 0;
                    // visit[i][j] = true;
                }
            }
        }

        while(!queue.isEmpty()) {
            int size = queue.size(); // 每个源点只能同时向前走一步
            while(size-- != 0) {
                // 取出点
                int[] point = queue.poll();
                // 分解点坐标
                int Ox = point[0];
                int Oy = point[1];

                // 遍历下一层节点
                for(int i = 0; i < 4; i++) {
                    int x = Ox + dx[i];
                    int y = Oy + dy[i];

                    if(x >= 0 && x < m && y >= 0 && y < n && dp[x][y] == -1) {
                        dp[x][y] = dp[Ox][Oy] + 1;
                        // visit[x][y] = true;
                        queue.offer(new int[]{x, y});
                    }
                }
            }
        }
        return dp;
    }
}
